package com.jhy.suixianglu.daima20221228;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 三数之和
 */
public class ThreeSum {
    public List<List<Integer>> threeSum(int[] nums) {
        // 首先定义一个结果集 来返回我们的结果
        ArrayList<List<Integer>> res = new ArrayList<>();
        // 给nums进行排序
        Arrays.sort(nums);
        for (int index = 0; index < nums.length; index++) {
            // 排序之后如果第一个元素大于0了 就直接返回
            if (nums[index] > 0) {
                return res;
            }
            // 首先判断index这个位置上是否有重复的元素
            if (index > 0 && nums[index] == nums[index - 1]) {
                continue;
            }
            // 定义left和right指针
            int right = nums.length - 1;
            int left = index + 1;
            // 然后进行每一个的循环
            while (left < right) {
                // 说明当前范围大了 故要减少right的范围
                if (nums[index] + nums[left] + nums[right] > 0) {
                    right--;
                } else if (nums[index] + nums[left] + nums[right] < 0) {
                    // 范围小了 要加大left的范围
                    left++;
                } else {
                    // todo 这里中间应该是以逗号连接的
                    res.add(Arrays.asList(nums[index] ,nums[left] , nums[right]));
                    // 后面开始进行去重 对right和left位置上的数值进行去重
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    // 对else里面的数值进行 流程控制
                    // 因为这里已经找到了 两个指针都要移动
                    left++;
                    right--;
                }
            }
        }
        return res;

    }
}
